/*  
 *  Copyright 2006 Paul Jack.
 *
 *  This file is part of the Dex compiler suite. 
 *  
 *  Dex is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the
 *  Free Software Foundation; either version 2 of the License, or (at your
 *  option) any later version.
 *  
 *  Dex is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
 *  Public License for more details.
 *  
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */
package dex.compiler.parser;

import java.util.ArrayList;
import java.util.List;

import dex.compiler.model.base.Place;
import dex.compiler.model.expression.ArrayExpression;
import dex.compiler.model.expression.DirectCall;
import dex.compiler.model.expression.IndirectCall;
import dex.compiler.model.expression.CastExpression;
import dex.compiler.model.expression.Expression;
import dex.compiler.model.expression.IdentifierExpression;
import dex.compiler.model.expression.Infix;
import dex.compiler.model.expression.InfixExpression;
import dex.compiler.model.expression.IsExpression;
import dex.compiler.model.expression.LiteralBoolean;
import dex.compiler.model.expression.MemberExpression;
import dex.compiler.model.expression.NewExpression;
import dex.compiler.model.expression.Unary;
import dex.compiler.model.expression.UnaryExpression;
import dex.compiler.model.expression.VirtualCall;
import dex.compiler.model.type.ArrayTypeNode;
import dex.compiler.model.type.TypeNode;


/**
 * Parser for Expression objects.
 */
class ExpressionParser extends LiteralParser {

	
	
	/**
	 * A simple linked list of operator expressions.
	 * One could consider this prefix notation.
	 * It makes it easy to reorder the terms into infix operators
	 * with precedence.
	 */
	private static class OperatorNode {
		public Infix operator;
		public Expression operand;
		public OperatorNode next;
		public OperatorNode(Infix operator, Expression operand, OperatorNode next) {
			this.operator = operator;
			this.operand = operand;
			this.next = next;
		}
	}

	
	
	/**
	 * Constructs a new ExpressionParser.
	 * 
	 * @param config  the configuration for the new parser
	 */
	public ExpressionParser(ParserConfig config) {
		super(config);
	}


	/**
	 * Parses a new expression.
	 * 
	 * @return  the parsed new expression
	 */
	public NewExpression parseNewExpression() {
		input.skip();
		Place place = input.getPlace();
		input.expect("new", WordBreaks.INSTANCE);
		TypeNode type = parseBaseType();

		char ch = input.skipAndPeek();
		if (ch == '(') {
			return new NewExpression(place, type, parseExpressionList());		
		} else if (ch == '[') {
			List<Expression> params = parseExpressionList('[', ']');
			if (params.isEmpty()) {
				type = new ArrayTypeNode(input.getPlace(), type);
			} else {
				for (int i = params.size() - 1; i >= 0; i--) {
					type = new ArrayTypeNode(input.getPlace(), type);
				}
			}
			return new NewExpression(place, type, params);
		} else {
			raise("Expected construction parameters.");
			throw new AssertionError();
		}
	}

	
	/**
	 * Parses an expression list.  An expression list starts with 
	 * an open parenthesis, contains expressions separated by commas,
	 * and ends with a closed parenthesis.  This method is used to
	 * parse function call parameters, for instance.
	 * 
	 * @return the parsed expression list
	 */
	public List<Expression> parseExpressionList() {
		return parseExpressionList('(', ')');
	}
	
	
	/**
	 * Parses an expression list delimited by the given characters.
	 * Expressions in the list are separated by commas.
	 * 
	 * @return the parsed expression list
	 * @start  the starting character, eg '('
	 * @end    the ending character, eg ')'
	 */
	private List<Expression> parseExpressionList(char start, char end) {
		char ch = input.skipAndRead();
		if (ch != start) {
			raise("Expected expression list.");
		}

		List<Expression> result = new ArrayList<Expression>();

		ch = input.skipAndPeek();
		if (ch == end) {
			input.expect(end);
			return result;
		}
		
		result.add(parseExpression());
		ch = input.skipAndPeek();
		while (ch == ',') {
			input.expect(',');
			result.add(parseExpression());
			ch = input.skipAndPeek();
		}
		input.skipAndExpect(end);
		
		return result;
	}


	/**
	 * Parses a unary expression.
	 * 
	 * @return  the parsed unary expression
	 */
	public UnaryExpression parseUnaryExpression() {
		String symbol = input.skipAndTest(Unary.SYMBOLS, AnyBreaks.INSTANCE);
		input.expect(symbol, AnyBreaks.INSTANCE);
		if (symbol == null) {
			throw new ParseException(input.getPlace(), "Expected unary operator.");
		}
		Unary op = Unary.get(symbol);
		return new UnaryExpression(input.getPlace(), op, parseOperand());
	}


	/**
	 * Parses an expression that could be used in an infix operator.
	 * The return value might be something as simple as <code>3</code>,
	 * but could be as complicated as:
	 * 
	 * <pre>
	 * foo.bar[5]().baz(4 + 5, 7 + 9)
	 * </pre>
	 * 
	 * As the above example shows, this method does not guarantee that
	 * "internal" expressions won't contain infix operators, just that
	 * the returned expression will not be an OperatorExpression.
	 * 
	 * @return  the parsed operand expression
	 */
	private Expression parseOperand() {
		Expression result;
		char ch = input.skipAndPeek();
		if (testKeyword("new")) {
			result = parseNewExpression();
		} else if (testKeyword("cast")) {
			input.expect("cast", WordBreaks.INSTANCE);
			input.skipAndExpect('(');
			Expression value = parseExpression();
			input.skipAndExpect(',');
			TypeNode type = parseType();
			input.skipAndExpect(')');
			result = new CastExpression(input.getPlace(), type, value);
		} else if (testKeyword("is")) {
			input.expect("is", WordBreaks.INSTANCE);
			input.skipAndExpect('(');
			Expression value = parseExpression();
			input.skipAndExpect(',');
			TypeNode type = parseType();
			input.skipAndExpect(')');
			result = new IsExpression(input.getPlace(), type, value);			
		} else if (input.test(Unary.SYMBOLS, AnyBreaks.INSTANCE) != null) {
			result = parseUnaryExpression();
		} else if (ch == '$') {
			result = parseFunctionLiteral();
		} else if (ch == '(') {
			input.expect('(');
			result = parseExpression();
			input.expect(')');
		} else if (ch == '\"') {
			result = parseLiteralString();
		} else if (Character.isDigit(ch)) {
			result = parseLiteralInteger();
		} else if (Character.isJavaIdentifierStart(ch)) {
			String id = parseIdentifier();
			if (input.peek() == '(') {
				result = new DirectCall(input.getPlace(), id, parseExpressionList());
			} else if (id.equals("true")) {
				result = new LiteralBoolean(input.getPlace(), true);
			} else if (id.equals("false")) {
				result = new LiteralBoolean(input.getPlace(), false);
			} else {
				result = new IdentifierExpression(input.getPlace(), id);
			}
		} else {
			raise("Expected operand.");
			result = null; // FIXME: This statement never reached
		}
		result = parseOperandTail(result);
		return result;
	}
	
	
	/**
	 * Parses an operand tail.  An operand can be followed by any sequence
	 * of Member, Call or Array expressions.  Eg:
	 * 
	 * <pre>
	 * x.foo()[5]
	 * </pre>
	 * 
	 * The <code>x</code> is something that parseOperand would discover,
	 * but before returning just a simple IdentifierExpression back to the
	 * caller, parseOperand invokes parseOperandTail to ensure that 
	 * any "postfix operators" are applied.
	 * 
	 * @param original  the original expression returned by parseOperand
	 * @return  that expression nested with any following Member, Call or 
	 *   Array expressions
	 */
	protected Expression parseOperandTail(Expression original) {
		char ch = input.skipAndPeek();
		Expression result;
		if (ch == '.') {
			input.expect('.');
			String memberName = parseIdentifier();
			if (input.peek() == '(') {
				result = new VirtualCall(input.getPlace(), original, memberName, parseExpressionList());
			} else {
				result = new MemberExpression(input.getPlace(), original, memberName);
			}
			result = parseOperandTail(result);
			return result;
		} else if (ch == '[') {
			input.expect('[');
			Expression index = parseExpression();
			input.expect(']'); // FIXME: Multidimensionals
			result = new ArrayExpression(input.getPlace(), original, index);
			result = parseOperandTail(result);
			return result;
		} else if (ch == '\\') {
			input.expect('\\');
			List<Expression> parameters = parseExpressionList();
			result = new IndirectCall(input.getPlace(), original, parameters);
			result = parseOperandTail(result);
			return result;
		}
		return original;
	}

	
	/**
	 * Convenience for picking an operator.  Makes parseInfox a bit easier 
	 * to follow.
	 */
	protected String pickOperator() {
		String s = input.skipAndTest(Infix.SYMBOLS, SymbolBreaks.INSTANCE);
		if (s == null) {
			return null;
		}
		input.expect(s, SymbolBreaks.INSTANCE);
		return s;
	}

	
	/**
	 * Parses one or more infix operator expressions.  This method ensures
	 * that the returned tree of OperatorExpression nodes is ordered according
	 * to operator precedence rules.
	 * 
	 * @param firstTerm  the first operand for the operator expression tree
	 * @return  the operator expression in proper order
	 * 
	 */
	private Expression parseInfix(Expression firstTerm) {
		OperatorNode head = new OperatorNode(null, firstTerm, null);
		
		OperatorNode current = head;
		String symbol = pickOperator();
		while (symbol != null) {
			Infix op = Infix.get(symbol);
			current.next = new OperatorNode(op, parseOperand(), null);
			current = current.next;
			symbol = pickOperator();
		}
		
		// Collapse list into OperatorExpression tree that is sorted by
		// operator priority
		//
		// Eg, 5 + 2 * 3 should become (2 * 3) + 5
		for (int priority = Infix.MAX_PRIORITY; priority >= 0; priority--) {
			OperatorNode previous = head;
			current = head.next;
			while (current != null) {
				if (current.operator.getPriority() == priority) {
					previous.operand = new InfixExpression(input.getPlace(), current.operator, previous.operand, current.operand);
					previous.next = current.next;
					current = previous.next;
				} else {
					previous = current;
					current = current.next;
				}
			}
		}
		
		return head.operand;
	}

	
	/**
	 * Parses an expression.
	 * 
	 * @return the parsed expression
	 */
	public Expression parseExpression() {
		Expression term = parseOperand();
		if (input.test(Infix.SYMBOLS, SymbolBreaks.INSTANCE) != null) {
			return parseInfix(term);
		} else {
			return term;
		}
	}
}
